//! @Author: DengLibin
//! @Date: Create in 2024-01-29 14:50:51
//! @Description: 栈

/// @Author: DengLibin
/// @Date: Create in 2024-01-29 14:59:03
/// @Description: 使用vec实现一个栈
struct Stack<T> {
    top: usize,   //栈顶
    data: Vec<T>, // 数据容器
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack {
            top: 0,
            data: Vec::new(),
        }
    }

    //入栈
    fn push(&mut self, val: T) {
        self.data.push(val);
        self.top += 1;
    }
    //弹栈
    fn pop(&mut self) -> Option<T> {
        if self.top == 0 {
            return None;
        }
        self.top -= 1;
        self.data.pop()
    }

    fn peek(&self) -> Option<&T> {
        if self.top == 0 {
            return None;
        }
        self.data.get(self.top - 1)
    }

    fn is_empty(&self) -> bool {
        0 == self.top
    }

    fn size(&self) -> usize {
        self.top
    }
}

//括号是否匹配
fn par_match(open: char, close: char) -> bool {
    let opens = "([{";
    let closes = ")]}";
    return opens.find(open) == closes.find(close);
}

//栈应用1： 括号匹配
fn par_chek(par: &str) -> bool {
    let mut stack = Stack::new(); //创建一个栈
    for c in par.chars() {
        //左括号
        if '(' == c || '[' == c || '{' == c {
            stack.push(c);
        } else {
            //右括号
            if stack.is_empty() {
                return false;
            }
            let top = stack.pop().unwrap();
            if !par_match(top, c) {
                return false;
            }
        }
    }

    return true;
}

//栈应用2： 进制转换
fn base_convert(mut dec_num: u32, base: u32) -> String {
    // digits 对应各种余数的字符形式，尤其是 10 - 15
    let digits = [
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
    ];

    let mut stack = Stack::new();
    //余数入栈
    while dec_num > 0 {
        let rem = dec_num % base;
        stack.push(digits[rem as usize]);
        dec_num = dec_num / base;
    }
    //余数出栈
    let mut s = String::new();
    while !stack.is_empty() {
        s.push(stack.pop().unwrap());
    }
    return s;
}

pub fn hello_stack() {
    let b = par_chek("{(([]))}");
    println!("括号匹配:{}", b);

    let bin = base_convert(8, 2);
    println!("十进制:{}, 二进制:{}", 8, bin);

    let bin = base_convert(32, 16);
    println!("十进制:{}, 16进制:{}", 32, bin);

}
